#include "manifest.h"

queue_t* queue_append(queue_t* head, queue_t* elem) {
    if (head == null) {
        head = elem->next = elem->back = elem;
    } else {
        assert(head->back->next == head && head->next->back == head);
        queue_t* back = head->back;
        elem->next = head;
        elem->back = back;
        head->back = elem;
        back->next = elem;
        assert(elem->back->next == elem && elem->next->back == elem);
    }
    assert(head->back->next == head && head->next->back == head);
    return head;
}

static void list(const char* label, queue_t* q) {
//  trace("%s", label);
    if (q != null) {
        queue_t* i = q;
        do {
//          trace("%s <- %s -> %s", i->back->data, i->data, i->next->data);
            i = i->next;
        } while (i != q);
    } else {
//      trace("queue is empty");
    }
}

queue_t* queue_remove(queue_t* head) {
    assert(head != null && head->back->next == head && head->next->back == head);
    queue_t* back = head->back;
    queue_t* next = back != head ? head->next : null;
    if (next != null) {
//      trace("next=%s", next->data);
        back->next = next;
        next->back = back;
//      list("queue_remove after", next);
    }
    head->back = head->next = null;
    assert(next == null || next->back->next == next && next->next->back == next);
    return next;
}

static queue_t* s2e(const char* s) {
    queue_t* e = (queue_t*)mem_alloc(sizeof(queue_t));
    e->data = (void*)s;
    e->bytes = 1;
}

void queue_smoke_test() {
    int64 ad = mem_allocated();
    int64 as = mem_allocations();
    static const char* a[4]= {"a", "b", "c", "d"};
    queue_t* q = null;
    for (int i = 0; i < countof(a); i++) {
//      trace("appending %s", a[i]);
        q = queue_append(q, s2e(a[i]));
//      list("after append", q);
    }
    for (int i = 0; i < countof(a); i++) {
        queue_t* e = q;
        assert(e != null && strcmp((const char*)e->data, a[i]) == 0);
//      trace("removing %s", e->data);
        q = queue_remove(q);
        mem_free(e);
//      list("after remove", q);
    }
    assert(q == null);
    assertion(ad == mem_allocated() && as == mem_allocations(),
             "ad=%lld mem_allocated()=%lld as=%lld mem_allocates()=%lld",
             ad, mem_allocated(), as, mem_allocations());
}
